//147.对链表进行插入排序
//https://leetcode.cn/problems/insertion-sort-list/
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* rethead = head;
        ListNode* cur = head->next;
        rethead->next = nullptr;

        while(cur)
        {
            ListNode* ins = cur;
            cur = cur->next;
            ins->next = nullptr;
            if(ins->val <= rethead->val)
            {
                ins->next = rethead;
                rethead = ins;
            }
            else
            {
                ListNode* prev = rethead;
                ListNode* tail = prev->next;
                while(tail && tail->val < ins->val)
                {
                    prev = tail;
                    tail = tail->next;
                }
                ins->next = prev->next;
                prev->next = ins;
            }
        }
        return rethead;
    }
};